# -*- coding: utf-8 -*-
"""
Created on Mon Feb 13 22:47:46 2017

@author: CY_XYZ
"""

import random


# =======================================================
# =======  Item类，包含Item编号、周期时长、在缓存中的索引ID
# =======      
# ======================================================= 
class Item:
    # 初始化节点:属性id为Item的唯一编号
    #           属性age为item的周期时长
    #           属性nextItem为当前Item的后继Item
    #              如有需要，可用于进行队列插入、删除后更新队列
    #              但本程序属于随机模拟，用不到此属性
    #           属性indexID为Item在缓存空间中的位置，即缓存空间占用索引编号
    def __init__(self, ID, IndexID):
        self.id = ID
        self.age = 0
        self.nextItem = []
        self.indexID = -1


# =======================================================
# =======  淘汰操作API，判断缓存空间是否满，为增加Item操作保障空间
# =======              将最接近队首且周期时长大于10的Item淘汰
# =======              输入参数：缓存空间队列CacheList
# =======                       占用缓存空间索引列表list_Index
# =======              返回参数：更新后的占用缓存空间索引列表
# ======================================================= 
def drop(CacheList, list_Index):
    # CacheLength保存当前缓存空间已被占用的长度
    CacheLength = len(list_Index)
    # firstItem_index为缓存空间队首Item的占用索引编号
    firstItem_Index = list_Index[0]
    print(">>>>>>淘汰前占用缓存空间索引列表：", list_Index)
    # 先判断缓存空间是否被占满，保障Item添加操作
    if CacheLength == len(CacheList):
        print("----缓存占满淘汰队首%d----" % CacheList[firstItem_Index].id)
        # 将被淘汰的Item的占用索引编号，从占用缓存空间索引列表中剔除
        # 这相当于更新占用缓存空间索引列表
        list_Index.remove(firstItem_Index)
        # 再对被淘汰的Item所占用的缓存空间作初始化操作
        # 并将此Item的编号设置为-1，做已被淘汰标记
        CacheList[firstItem_Index].__init__(ID=-1, IndexID=-1)
        print(">>>>>>>>淘汰后检测索引列表", list_Index)
        # 将更新后的占用缓存空间索引列表返回
        return list_Index
    else:
        # 利用当前的占用缓存空间索引列表
        # 从左至右顺序遍历占用缓存空间的Item
        # 一旦发现当前Item的周期时长大于10，将此Item淘汰，结束遍历
        for i in list_Index:
            if CacheList[i].age > 10:
                print("------Item编号%d因周期超时而被淘汰" % CacheList[i].indexID)
                # 更新占用缓存空间索引列表
                list_Index.remove(i)
                # 再对被淘汰的Item所占用的缓存空间作初始化操作
                # 并将此Item的编号设置为-1，做已被淘汰标记
                CacheList[i].__init__(ID=-1, IndexID=-1)

                # 【由于每次只能删除一个Item】，因而优先删除最靠近队首的Item
                # break缩进在周期时长是否大于10的判断内！！！！
                break
        print(">>>>>>>>淘汰后检测索引列表", list_Index)
        return list_Index


# =======================================================
# =======  添加操作API，先执行淘汰操作API，保证有可用缓存空间
# =======              输入参数：缓存空间队列CacheList
# =======                       占用缓存空间索引列表list_Index
# =======                       待添加的Item的唯一编号maxID
# =======              返回参数：更新后的占用缓存空间索引列表
# ======================================================= 
def add(CacheList, list_Index, maxID):
    # 添加新的Item前，先执行检查及淘汰操作
    # 检查缓存空间是否满；淘汰周期超时且最接近队首的Item或缓存空间已满下的队首Item
    # 以此保障一定有缓存空间添加新的Item

    # 执行淘汰操作API，得到更新后的占用空间索引列表
    list_Index = drop(CacheList, list_Index)
    # 淘汰Item后再随机添加新的Item
    # 逆向思维考虑：相当于在CacheList中随机选取其空余空间

    # spareIndex表示缓存空间可用的占用索引
    spareIndex = [i for i in range(len(CacheList)) if not i in list_Index]
    # 从可用的占用索引中随机选取1个
    insert_Index = random.sample(spareIndex, 1)[0]
    # 更新占用缓存空间列表CacheList
    # 保存新添加的Item的唯一编号、缓存空间的占用索引
    CacheList[insert_Index].id = maxID
    CacheList[insert_Index].indexID = insert_Index

    # 执行更新操作API，返回的是最新的占用缓存空间索引列表list_Index
    return structure_update(CacheList)


# =======================================================
# =======  更新操作API，监视当前的缓存空间被占用的情况
# =======              输入参数：缓存空间队列CacheList
# =======              返回参数：更新后的占用缓存空间索引列表
# ======================================================= 
# 在随机空间中确定Item在CacheList中的相对排列顺序
def structure_update(CacheList):
    # 保存缓存空间被占用的索引列表
    list_Index = [i for i in range(100) if CacheList[i].indexID != -1]
    print("----占用缓存空间索引列表----\n", list_Index)
    # 保存当前缓存空间被占用的长度
    CacheLength = len(list_Index)
    print("----占用缓存空间长度：", CacheLength)
    print("占用缓存空间Item信息如下：")

    # 将当前缓存空间中存在的Item构建成单向链表
    # 本模拟程序可此步骤
    for i in range(CacheLength - 1):
        CacheList[list_Index[i]].nextItem = CacheList[list_Index[i + 1]]
        print("ID编号", CacheList[list_Index[i]].id, "--周期时长", CacheList[list_Index[i]].age)
    CacheList[list_Index[CacheLength - 1]].nextItem = []

    # 返回最新的占用空间索引列表list_Index
    return list_Index


# =======================================================
# =======  主函数，初始化：
# =======        从0~99随机选取50个整数作为初始状态下，50个Item所占据的缓存空间分布
# =======        随机排列0~49，然后以此对应占据缓存空间的Item-ID编号

# ======================================================= 
# initIDSeq为初始状态下50个Item之间的相对位置随机序列
initIDSeq = random.sample(range(50), 50)
# initListIndex：在缓存空间【100个】中随机选取【50个】，作为初始占用缓存空间索引列表
initListIndex = random.sample(range(100), 50)
# 构造缓存空间CacheList，默认大小100，CacheList中容纳的是Item对象
CacheList = []
for i in range(100):
    CacheList.append(Item(ID=i, IndexID=-1))

# 初始化50个Item的属性：唯一编号、周期时长、占用缓存空间索引编号
for i, id in zip(initListIndex, initIDSeq):
    CacheList[i].ID = id
    CacheList[i].age = random.randint(0, 10)
    CacheList[i].indexID = i
# 调用更新操作API，获取当前最新的缓存空间占用索引列表list_Index
list_Index = structure_update(CacheList)

# 设置模拟次数，默认200
Time = 200
# 开启模拟测试
while Time:

    print("========time-%d========" % (200 - Time))
    print("=========本次循环占用缓存空间Item起始周期时长列表：")
    for i in list_Index:
        CacheList[i].age += 1
        print(CacheList[i].age, end='-')
    print("--------------------------------\n")

    # 计算本次应添加的Item的唯一编号
    maxID = 250 - Time
    # 调用添加API
    list_Index = add(CacheList, list_Index, maxID)
    # 循环变量递减，逐步逼近循环结束条件
    Time -= 1

"""
运行结果部分：
========time-197========
=========本次循环占用缓存空间Item起始周期时长列表：
6-11-8-2-10-3-9-4-7-1-5-199-185-207-119-198-182-206-203-206-196-205-204-206-201-208-162-201-49-179-201-155-207-206-181-204-190-58-203-189-200-207-152-171-208-201-204-81-186-191---------------------------------

>>>>>>淘汰前占用缓存空间索引列表： [1, 8, 13, 14, 15, 22, 23, 29, 33, 36, 54, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
------Item编号8因周期超时而被淘汰
>>>>>>>>淘汰后检测索引列表 [1, 13, 14, 15, 22, 23, 29, 33, 36, 54, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
----占用缓存空间索引列表----
 [1, 13, 14, 15, 20, 22, 23, 29, 33, 36, 54, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
----占用缓存空间长度： 50
占用缓存空间Item信息如下：
ID编号 241 --周期时长 6
ID编号 239 --周期时长 8
ID编号 245 --周期时长 2
ID编号 237 --周期时长 10
ID编号 247 --周期时长 0
ID编号 244 --周期时长 3
ID编号 238 --周期时长 9
ID编号 243 --周期时长 4
ID编号 240 --周期时长 7
ID编号 246 --周期时长 1
ID编号 242 --周期时长 5
ID编号 61 --周期时长 199
ID编号 62 --周期时长 185
ID编号 63 --周期时长 207
ID编号 128 --周期时长 119
ID编号 65 --周期时长 198
ID编号 65 --周期时长 182
ID编号 67 --周期时长 206
ID编号 68 --周期时长 203
ID编号 69 --周期时长 206
ID编号 51 --周期时长 196
ID编号 71 --周期时长 205
ID编号 72 --周期时长 204
ID编号 73 --周期时长 206
ID编号 74 --周期时长 201
ID编号 75 --周期时长 208
ID编号 85 --周期时长 162
ID编号 77 --周期时长 201
ID编号 198 --周期时长 49
ID编号 68 --周期时长 179
ID编号 80 --周期时长 201
ID编号 92 --周期时长 155
ID编号 82 --周期时长 207
ID编号 83 --周期时长 206
ID编号 66 --周期时长 181
ID编号 85 --周期时长 204
ID编号 57 --周期时长 190
ID编号 189 --周期时长 58
ID编号 88 --周期时长 203
ID编号 58 --周期时长 189
ID编号 90 --周期时长 200
ID编号 91 --周期时长 207
ID编号 95 --周期时长 152
ID编号 76 --周期时长 171
ID编号 94 --周期时长 208
ID编号 95 --周期时长 201
ID编号 96 --周期时长 204
ID编号 166 --周期时长 81
ID编号 61 --周期时长 186
========time-198========
=========本次循环占用缓存空间Item起始周期时长列表：
7-9-3-11-1-4-10-5-8-2-6-200-186-208-120-199-183-207-204-207-197-206-205-207-202-209-163-202-50-180-202-156-208-207-182-205-191-59-204-190-201-208-153-172-209-202-205-82-187-192---------------------------------

>>>>>>淘汰前占用缓存空间索引列表： [1, 13, 14, 15, 20, 22, 23, 29, 33, 36, 54, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
------Item编号15因周期超时而被淘汰
>>>>>>>>淘汰后检测索引列表 [1, 13, 14, 20, 22, 23, 29, 33, 36, 54, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
----占用缓存空间索引列表----
 [1, 13, 14, 20, 22, 23, 29, 33, 36, 48, 54, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
----占用缓存空间长度： 50
占用缓存空间Item信息如下：
ID编号 241 --周期时长 7
ID编号 239 --周期时长 9
ID编号 245 --周期时长 3
ID编号 247 --周期时长 1
ID编号 244 --周期时长 4
ID编号 238 --周期时长 10
ID编号 243 --周期时长 5
ID编号 240 --周期时长 8
ID编号 246 --周期时长 2
ID编号 248 --周期时长 0
ID编号 242 --周期时长 6
ID编号 61 --周期时长 200
ID编号 62 --周期时长 186
ID编号 63 --周期时长 208
ID编号 128 --周期时长 120
ID编号 65 --周期时长 199
ID编号 65 --周期时长 183
ID编号 67 --周期时长 207
ID编号 68 --周期时长 204
ID编号 69 --周期时长 207
ID编号 51 --周期时长 197
ID编号 71 --周期时长 206
ID编号 72 --周期时长 205
ID编号 73 --周期时长 207
ID编号 74 --周期时长 202
ID编号 75 --周期时长 209
ID编号 85 --周期时长 163
ID编号 77 --周期时长 202
ID编号 198 --周期时长 50
ID编号 68 --周期时长 180
ID编号 80 --周期时长 202
ID编号 92 --周期时长 156
ID编号 82 --周期时长 208
ID编号 83 --周期时长 207
ID编号 66 --周期时长 182
ID编号 85 --周期时长 205
ID编号 57 --周期时长 191
ID编号 189 --周期时长 59
ID编号 88 --周期时长 204
ID编号 58 --周期时长 190
ID编号 90 --周期时长 201
ID编号 91 --周期时长 208
ID编号 95 --周期时长 153
ID编号 76 --周期时长 172
ID编号 94 --周期时长 209
ID编号 95 --周期时长 202
ID编号 96 --周期时长 205
ID编号 166 --周期时长 82
ID编号 61 --周期时长 187
========time-199========
=========本次循环占用缓存空间Item起始周期时长列表：
8-10-4-2-5-11-6-9-3-1-7-201-187-209-121-200-184-208-205-208-198-207-206-208-203-210-164-203-51-181-203-157-209-208-183-206-192-60-205-191-202-209-154-173-210-203-206-83-188-193---------------------------------

>>>>>>淘汰前占用缓存空间索引列表： [1, 13, 14, 20, 22, 23, 29, 33, 36, 48, 54, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
------Item编号23因周期超时而被淘汰
>>>>>>>>淘汰后检测索引列表 [1, 13, 14, 20, 22, 29, 33, 36, 48, 54, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
----占用缓存空间索引列表----
 [1, 8, 13, 14, 20, 22, 29, 33, 36, 48, 54, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
----占用缓存空间长度： 50
占用缓存空间Item信息如下：
ID编号 241 --周期时长 8
ID编号 249 --周期时长 0
ID编号 239 --周期时长 10
ID编号 245 --周期时长 4
ID编号 247 --周期时长 2
ID编号 244 --周期时长 5
ID编号 243 --周期时长 6
ID编号 240 --周期时长 9
ID编号 246 --周期时长 3
ID编号 248 --周期时长 1
ID编号 242 --周期时长 7
ID编号 61 --周期时长 201
ID编号 62 --周期时长 187
ID编号 63 --周期时长 209
ID编号 128 --周期时长 121
ID编号 65 --周期时长 200
ID编号 65 --周期时长 184
ID编号 67 --周期时长 208
ID编号 68 --周期时长 205
ID编号 69 --周期时长 208
ID编号 51 --周期时长 198
ID编号 71 --周期时长 207
ID编号 72 --周期时长 206
ID编号 73 --周期时长 208
ID编号 74 --周期时长 203
ID编号 75 --周期时长 210
ID编号 85 --周期时长 164
ID编号 77 --周期时长 203
ID编号 198 --周期时长 51
ID编号 68 --周期时长 181
ID编号 80 --周期时长 203
ID编号 92 --周期时长 157
ID编号 82 --周期时长 209
ID编号 83 --周期时长 208
ID编号 66 --周期时长 183
ID编号 85 --周期时长 206
ID编号 57 --周期时长 192
ID编号 189 --周期时长 60
ID编号 88 --周期时长 205
ID编号 58 --周期时长 191
ID编号 90 --周期时长 202
ID编号 91 --周期时长 209
ID编号 95 --周期时长 154
ID编号 76 --周期时长 173
ID编号 94 --周期时长 210
ID编号 95 --周期时长 203
ID编号 96 --周期时长 206
ID编号 166 --周期时长 83
ID编号 61 --周期时长 188

"""
